package 动态规划;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-19
 */
public class 斐波那契数列 {
   static int count = 1;
    public static void main(String[] args) {
        fib(10);
    }
    //时间复杂度为n^2
   static int fib(int N) {
       System.out.println(count++);
        if (N == 1 || N == 2) return 1;
        return fib(N - 1) + fib(N - 2);
    }

    //添加备忘录，减少重复的递归
    //时间复杂度为n
    int fibWithMemo(int N) {
        int[] memo = new int[N];
        return fibWithMemo(N, memo);
    }

    //自顶向下
    private int fibWithMemo(int N, int[] memo) {
        if (N == 1 || N == 2) {
            return 1;
        }
        if (memo[N] == 0) {
            memo[N] = fibWithMemo(N - 1, memo) + fibWithMemo(N - 2, memo);
        }
        return memo[N];
    }

    //通过dp，自底向上
    private int fibWithDp(int N) {
        int[] memo = new int[N];
        memo[1] = memo[2] = 1;
        for (int i = 3; i <= N; i++) {
            memo[i] = memo[i - 1] + memo[i - 2];
        }
        return memo[N];
    }
    //通过空间复杂度为1
    int fibWith1O(int n) {
        if (n == 2 || n == 1) return 1;
        int prev = 1, curr = 1;
        for (int i = 3; i <= n; i++) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }
}
